#include "CostumUtils.h"
#include <vector>

using std::vector;

void merge(vector<int> & list, int start, int mid, int end);

/*
      a, b, c, d
	      /\
		 /  \
	  a, b   c, d
	   /\     /\
	  /  \   /  \
	 a    b c    d
*/
void mergeSorted(vector<int> & list, int start, int end)
{
	if (end > start) {
		int mid = (end + start) / 2;
		mergeSorted(list, start, mid);
		mergeSorted(list, mid + 1, end);
		merge(list, start, mid, end);
	}
}

void merge(vector<int> & list, int start, int mid, int end)
{
	vector<int> left;
	vector<int> right;
	left.reserve(mid - start + 1);
	right.reserve(end - mid);

	for (int i = start; i <= mid; i++) left.push_back(list[i]);
	for (int j = mid + 1; j <= end; j++) right.push_back(list[j]);
	left.push_back(INFTY);
	right.push_back(INFTY);

	int i = 0, j = 0;

	for (int k = start; k <= end; k++) {
		if (left[i] > right[j]) {
			list[k] = right[j];
			j++;
		} else {
			list[k] = left[i];
			i++;
		}
	}
}